Border basis detection is NP-complete

Border basis detection (BBD) is described as follows: given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. The motivation for this problem comes from a similar problem related to Grobner bases termed as Grobner basis detection (GBD) which was proposed by Gritzmann and Sturmfels (1993). GBD was shown to be NP-hard by Sturmfels and Wiegelmann (1996). In this paper, we investigate the computational complexity of BBD and show that it is NP-complete.

Cloning and development of pathotype-specific SCAR marker associated with Sclerospora graminicola isolates from pearl millet

Downy mildew pathogen of pearl millet in India is associated with the spread of the highly virulent Sclerospora graminicola pathotype-1. Twenty-seven S. graminicola isolates were screened using 20 intersimple sequence repeats (ISSR). Dinucleotide repeat primer [17898A-(CA)(6) AC] amplified a similar to 600 bp fragment specific to five isolates of pathotype-1 (Sg 048, Sg 153, Sg 212, DM-11 and DM-90). The ISSR fragment linked with pathotype-1 was cloned successfully and sequenced. To convert ISSR fragments into pathotype-specific sequence characterised amplified region (SCAR) markers, PCR primers were designed using a sequence of the cloned DNA fragment. PCR amplification using SCAR primer pair (UOM3-Sg-Path1-F/R) amplified a single 284 bp band only in isolates of S. graminicola pathotype-1. This SCAR primer pair did not amplify the 284 bp product from the other five S. graminicola pathotypes or a negative control, which demonstrates primer specificity for pathotype-1. The SCAR primer pair (UOM3-Sg-Path1-F/R) obtained in this study will provide a valuable tool for rapid identification and specific detection of S. graminicola pathotype-1.

On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k, where each R-i is a closed interval on the real line of the form [a(j), a(i), + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph. It is known that for graph G, cub(G) <= left perpendicular2n/3right perpendicular. Recently it has been shown that for a graph G, cub(G) >= 4(Delta + 1) In n, where n and Delta are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G = (A boolean OR B, E) with |A| = n(1), |B| = n2, n(1) <= n(2), and Delta' = min {Delta(A),Delta(B)}, where Delta(A) = max(a is an element of A)d(a) and Delta(B) = max(b is an element of B) d(b), d(a) and d(b) being the degree of a and b in G, respectively , cub(G) <= 2(Delta' + 2) bar left rightln n(2)bar left arrow. We also give an efficient randomized algorithm to construct the cube representation of G in 3 (Delta' + 2) bar right arrowIn n(2)bar left arrow dimension. The reader may note that in general Delta' can be much smaller than Delta.

Studies of Phosphazenes. Part 13.' Thermal Rearrangement Reactions of Some Met hoxycyclo phosp hazenes

The methoxycyclophosphazenes [NP(OMe),], (n = 3-6) rearrange on heating to give oxocyclophosphazanes, [N(Me)PO(OMe)],. Isomeric products are formed when n = 4-6. The lH, ,lP, and 13C n.m.r. data for the starting materials and the products are presented. The ethoxy- and n-propoxy-derivatives N,P,( OR)* do not undergo the above rearrangement. The geminal derivatives N,P,R,(OMe), (R = Ph or NHBut) on heating yield both fully and partially rearranged products, namely dioxophosphaz-1 -enes and oxophosphazadienes, as shown by 270- MHz lH n.m.r. spectroscopy. The non-geminal derivative N,P,( NMe,),(OMe), gives only the fully rearranged product N,Me,P,(NMe,),O,(OMe), whose structure has been established from its lH and 31P n.m.r. spectra.

Deformation mechanisms during large strain deformation of nanocrystalline nickel

In this letter, a conclusive evidence of the operation of planar slip along with grain boundary mediated mechanisms has been reported during large strain deformation of nanocrystalline nickel. Dislocation annihilation mechanism such as mechanical recovery has been found to play an important role during the course of deformation. The evidences rely on x-ray based techniques, such as dislocation density determination and crystallographic texture measurement as well as microstructural observation by electron microscopy. The characteristic texture evolution in this case is an indication of normal slip mediated plasticity in nanocrystalline nickel.

Unsteady flow of a dilute suspension in a semi-infinite contracting or expanding pipe

In the present paper an exact similar solution of the Navier-Stokes equation for unsteady flow of a dilute suspension in a semi-infinite contracting or expanding circular pipe is presented. The effects of the Schmidt number (Sc), Reynolds number (|ε|), the volume fraction (α) and the relaxation time (τ) of the particulate phase on the flow characteristics are examined. The presence of the solid particles has been observed to influence the flow behaviour significantly. These solutions are valid down to the state of a completely collapsed pipe, since the nonlinearity is retained fully. The results may help understanding the flow near the heart and certain forced contractions or expansions of valved veins.

New initiators for the ring-opening thermal polymerization of hexachlorocyclotriphosphazene: synthesis of linear poly(dichlorophosphazene) in high yields

Ring-opening thermal polymerization of hexachlorocyclotriphosphazene (N3P3C&h)a s been investigated at 250 "C and at 1.333-Pa pressure using chlorocyclotriphosphazenes N3P3C15(N=PPh3) and N3P3Cl,.,(NMe2), (n = 2-4), salt hydrates, triphenylphosphine, and benzoic acid as initiators. The linear poly (dich1orophosphazene) products are phenoxylated, and the phenoxy polymers are characterized by gel permeation chromatography and dilute solution viscometry. Among the various initiators investigated, CaS04.2H20b rings about a high conversion (>60%) of N3P3C&to the linear [NPC12], polymer which possesses a high molecular weight (>5 X lo6). The rationale for the choice of the initiators and possible mechanism(s) of polymerization is discussed. Several mixed substituent polymers, [NP(OPh),(OC6H4Me-p)2,1, and [NP(OPh),(OCHzCF3)2,]nh, ave been prepared and their thermal properties evaluated.

Laminar flow of a suspension in a curved pipe with varying curvature

The laminar flow of a fairly concentrated suspension (in which the volume fraction Z of the solid particles < 0.4) in a spatially varying periodically curved pipe has been examined numerically. Unlike the case of interacting suspension flows, the particles are found to flow in a well-mixed fashion, altering both the axial and circumferential velocities and consequently the fluid flux in the tube, depending on their diffusivity and inertia. The magnitude of shear stress at the wall is enhanced, suggesting that, if applied to vascular system, the vascular wall could be prone to ulceration during pathological situations like polycythemia. The delay in adaptation of the deviation in Poiseuille flow velocity to the curvature changes is also discussed in detail.

Comprehensive Path-sensitive Data-flow Analysis

Data-flow analysis is an integral part of any aggressive optimizing compiler. We propose a framework for improving the precision of data-flow analysis in the presence of complex control-flow. W initially perform data-flow analysis to determine those control-flow merges which cause the loss in data-flow analysis precision. The control-flow graph of the program is then restructured such that performing data-flow analysis on the resulting restructured graph gives more precise results. The proposed framework is both simple, involving the familiar notion of product automata, and also general, since it is applicable to any forward data-flow analysis. Apart from proving that our restructuring process is correct, we also show that restructuring is effective in that it necessarily leads to more optimization opportunities. Furthermore, the framework handles the trade-off between the increase in data-flow precision and the code size increase inherent in the restructuring. We show that determining an optimal restructuring is NP-hard, and propose and evaluate a greedy strategy. The framework has been implemented in the Scale research compiler, and instantiated for the specific problem of Constant Propagation. On the SPECINT 2000 benchmark suite we observe an average speedup of 4% in the running times over Wegman-Zadeck conditional constant propagation algorithm and 2% over a purely path profile guided approach.

Unsteady flow of a dilute suspension in a semi-infinite contracting or expanding pipe

In the present paper an exact similar solution of the Navier-Stokes equation for unsteady flow of a dilute suspension in a semi-infinite contracting or expanding circular pipe is presented. The effects of the Schmidt number (Sc), Reynolds number (|ε|), the volume fraction (α) and the relaxation time (τ) of the particulate phase on the flow characteristics are examined. The presence of the solid particles has been observed to influence the flow behaviour significantly. These solutions are valid down to the state of a completely collapsed pipe, since the nonlinearity is retained fully. The results may help understanding the flow near the heart and certain forced contractions or expansions of valved veins.

Distributed Scheduling for Multi-Hop Wireless Networks

We study the performance of greedy scheduling in multihop wireless networks where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. Optimal scheduling requires selecting independent sets of maximum aggregate price, but this problem is known to be NP-hard. We propose and evaluate a simple greedy heuristic. We suggest how the greedy heuristic can be implemented in a distributed manner. We evaluate an analytical bound in detail, for the special case of a line graph and also provide a loose bound on the greedy heuristic for the case of an arbitrary graph.

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

On the unsteady flow of a fairly concentrated suspension due to contracting or expanding walls of a tube

Consummating our earlier work [1], the unsteady flow of a fairly concentrated suspension due to a single contraction or expansion of the walls of a tube is studied. A comparison of the results obtained by using two different formulae for the additional drag terms in the governing equations has been made. A region of circulation in the flow field is observed when the volume fraction Z greater-or-equal, slanted 0.3, the Schmidt number Sc < 1 and the density ratio (density of the particulate phase/density of the fluid phase) > 1.

Pulsatile blood flow in a rigid pulmonary alveolar sheet with porous walls

This paper deals with the pulsatile blood flow in the lung alveolar sheets by idealizing each of them as a channel covered by porous media. As the blood flow in the lung is of low Reynolds number, a creeping flow is assumed in the channel. The analytical and numerical results for the velocity and pressure distribution in the porous medium are presented. The effect of an imposed slip condition is also studied. Comparisons with the corresponding results for the steady-state case are made at the end.